package review;

import org.junit.Test;

import java.util.Arrays;

/***
 * 堆排序
 */
public class HeapSort {
    @Test
    public void test() {
//        int[] nums = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
//        int[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
//        int[] nums = {5, 2, 3, 1};


        //下面这两个测试用例挺好的！
        int[] nums = {5, 2, 6};
//        int[] nums = {5, 6, 2};

        int[] newNums = heapSort(nums);
        System.out.println(Arrays.toString(newNums));
    }


//    堆排序
//    整个过程就分为两个步骤：
//    1)构建大根堆并输出堆顶元素
//    2)调整剩余元素为大根堆,继续输出堆顶，重复该过程直到所有元素输出完毕
//
/*    时间复杂度分析:
        前半部分在构建堆的时候，每个非叶子结点都需要与其孩子进行比较互换，最多进行两次比较和互换，所以时间复杂度是O(n)
        后半部分在正式排序的时候，第i次取堆顶元素并重建大根堆需要O(log2n),总共需要取n-1次堆记录，所以时间复杂度是 O(nlogn)
        所以总的时间复杂度为O(nlogn)
*/
    public int[] heapSort(int[] nums) {

        int []newNums = new int[nums.length + 1];
        System.arraycopy(nums, 0, newNums, 1, nums.length); //将原数组拷贝到
//        System.out.println(Arrays.toString(newNums));


        for (int i = (newNums.length - 1) / 2; i >= 1; i--) {
            heapAdjust(newNums, i, newNums.length-1);
        }

//        System.out.println(Arrays.toString(newNums));


        for (int i = newNums.length-1; i > 1; i--) {
            swap(newNums, 1, i);
            heapAdjust(newNums, 1, i - 1);
        }

        return Arrays.copyOfRange(newNums, 1, newNums.length);

    }



    /***
     * 调整 s...m 为大根堆
     * @param nums
     * @param s 起始位置
     * @param m 终止位置
     */
    public void heapAdjust(int[] nums, int s, int m) {
        int temp = nums[s];

//        for (int j = 2 * s; j < m; j *= 2) {
        for (int j = 2*s; j <= m; j *= 2) {         // 需要要写 = 比如如果结点只有一个孩子结点，也需要比较它们的大小

            if (j < m && nums[j] < nums[j + 1]) {  //因为前面的循环条件中会出现 j = m的情况，所以这里要有个前提条件 j<m
                j = j + 1;
            }

//            if (nums[s] > nums[j]) {
//                break;
//            }
            if (temp >= nums[j]) {  //要写 =
                break;
            }

            nums[s] = nums[j];
            s = j;
        }
        nums[s] = temp;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}